package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC813 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 当然也可以选用DFS：https://leetcode-cn.com/problems/largest-sum-of-averages/solution/java-cong-di-gui-dao-ji-yi-hua-di-gui-dao-dp-by-pp/
     * 我是是在困的不想动脑子了
     * @return:
     */
    class Solution {
        public double largestSumOfAverages(int[] nums, int t) {
            /**
             划分型dp
             状态定义：dp[i][j]：表示前i个数字划分为j组的最大数
             状态表示：dp[i][j]：推导出j状态，前面必须已经划分为j-1个状态，否则不成立
             但是前j-1个状态也需要[0...i)个数字去推，这就是子问题
             dp[i][j] = Math.max(dp[i][j], dp[i - k][j - 1] + ans / k);
             初始条件和边界条件：
             dp[i][i]：前i个数字划分为i组，只有一种情况，每个数字一组
             dp[i][1]：前i个数组划分为1组，只有一种情况，前i个数字之和/个数i
             计算顺序：
             dp[1][1]
             dp[2][1],dp[2][2]
             dp[3][1],dp[3][2],dp[3][3]
             ...
             dp[l][1],dp[l][2]...dp[l][min(l, t)] 注：l >= t
             return dp[l][t]
             */
            int len = nums.length;
            double[][] dp = new double[len + 1][len + 1];
            double res = 0;

            for (int i = 1; i <= len; i++) {
                res += nums[i - 1];
                dp[i][i] = res;
                dp[i][1] = res / i;
            }

            for (int i = 3; i <= len; i++) {
                for (int j = 2; j <= t && j < i; j++) {
                    double ans = 0;
                    for (int k = 1; k <= (i - j + 1); k++) {
                        ans += nums[i - k];
                        //dp往前推
                        dp[i][j] = Math.max(dp[i][j], dp[i - k][j - 1] + ans / k);
                    }
                }
            }
            return dp[len][t];
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC813 an = new LC813();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
